/*
题目: 接雨水Ⅱ
给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

https://leetcode.cn/problems/trapping-rain-water-ii/
 */
public class TrapRainWater {
    public static class Pair implements Comparable<Pair> {
        public int x, y, h;
        public Pair(int x, int y, int h) {
            this.x = x;
            this.y = y;
            this.h = h;
        }

        public int compareTo(Pair o) {
            return this.h - o.h;   // 构造小根堆
        }
    }
    int[][] dir = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 方向
    // 也可以压缩: int[] dir = new int[] {-1, 0, 1, 0, -1};

    public int trapRainWater(int[][] heightMap) {
        // 堆实现
        int row = heightMap.length;
        int col = heightMap[0].length;

        PriorityQueue<Pair> heap = new PriorityQueue<> ();
        boolean[][] visited = new boolean[row][col];   // 防止多次访问
        // 围栅栏, 先将 4 个边界作为围栏
        for (int i = 0; i < col; i++) {
            visited[0][i] = visited[row - 1][i] = true;
            heap.offer(new Pair(0, i, heightMap[0][i]));
            heap.offer(new Pair(row - 1, i, heightMap[row - 1][i]));
        }
        for (int i = 0; i < row; i++) {
            visited[i][0] = visited[i][col - 1] = true;
            heap.offer(new Pair(i, 0, heightMap[i][0]));
            heap.offer(new Pair(i, col - 1, heightMap[i][col - 1]));
        }

        int src = 0;
        while (!heap.isEmpty()) {
            Pair cur = heap.poll();

            int maxHeight = cur.h;
            for (int i = 0; i < 4; i++) {
                int nextX = cur.x + dir[i][0];
                int nextY = cur.y + dir[i][1];
                // 越界 或 已经访问过了
                if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col || visited[nextX][nextY])
                    continue ;

                visited[nextX][nextY] = true;  // 标记
                // 如果最小的围栏比较 小
                if (heightMap[nextX][nextY] > cur.h) {
                    heap.offer(new Pair(nextX, nextY, heightMap[nextX][nextY]));
                } else { // 如果最小的 围栏, 还是比较大, 那就可以灌水
                    // 注意这里, 虽然围栏的高度没有变化, 但是要更新围栏的位置, (换一种理解就是接水后的真实高度)
                    heap.offer(new Pair(nextX, nextY, cur.h));
                    src += cur.h - heightMap[nextX][nextY];
                }
            }
        }

        return src;
    }
    /*
    先把最外围的一圈作为围栏， 选择一个最低的围栏， 如果这个围栏的邻节点都比它大， 此围栏可删除，邻节点作为新的围栏；
    如果邻节点比它小， 那么邻节点可储蓄的水为 二者高度之差， 此时在邻节点设置围栏，高度为当前围栏高度即可。
    */
}
